package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 根据前序和后序遍历构造二叉树
 *
 * @Author: cookLee
 * @Date: 2024-02-22
 */
public class ConstructFromPrePost {

    /**
     * 主
     * \
     * 输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
     * 输出：[1,2,3,4,5,6,7]
     * \
     * 输入: preorder = [1], postorder = [1]
     * 输出: [1]
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        int[] preorder = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] postorder = new int[]{4, 5, 2, 6, 7, 3, 1};
        ConstructFromPrePost constructFromPrePost = new ConstructFromPrePost();
        constructFromPrePost.constructFromPrePost(preorder, postorder);
    }

    /**
     * 树形图
     */
    Map<Integer, Integer> treeMap = new HashMap<Integer, Integer>();

    /**
     * 分治
     *
     * @param preorder  预购
     * @param postorder 后者
     * @return {@link TreeNode}
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int len = preorder.length;
        //存储后序遍历数组中元素与其索引位置的对应关系,以便后续通过值快速定位到其在后序遍历数组中的位置。
        for (int i = 0; i < len; i++) {
            this.treeMap.put(postorder[i], i);
        }
        return this.helper(preorder, 0, len - 1, 0, len - 1);
    }

    /**
     * 帮手
     * 递归助手类
     *
     * @param preorder  预购
     * @param preLeft   左前
     * @param preRight  预右
     * @param postLeft  左侧帖子
     * @param postRight 右后
     * @return {@link TreeNode}
     */
    private TreeNode helper(int[] preorder, int preLeft, int preRight, int postLeft, int postRight) {
        //如果先序遍历的左边界大于右边界，则返回空节点，表示当前子树为空。
        if (preLeft > preRight) {
            return null;
        }
        //初始化左子树节点数量为0
        int leftCount = 0;
        //如果先序遍历的左边界小于右边界，则说明当前子树不为空，需要计算左子树节点数量
        if (preLeft < preRight) {
            //先序遍历数组中找到下一个根节点的位置，并计算出左子树的节点数量
            leftCount = this.treeMap.get(preorder[preLeft + 1]) - postLeft + 1;
        }
        //构建当前根节点，并递归构建左右子树
        return new TreeNode(preorder[preLeft], this.helper(preorder, preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1), this.helper(preorder, preLeft + leftCount + 1, preRight, postLeft + leftCount, preRight - 1));

    }

}
